package com.cqs.leetcode.math;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author lixiaowen
 * @create 2020-01-02
 */
public class Pow50 {

    /**
     * 二分法
     */
    static class Solution {
        public double myPow(double x, int n) {
            if (n == 0) return 1;
            if (x == 0) return 0;
            //符号位
            int sign = (n >> 31) & 0x1;
            double preHandle = 1;
            if (n == Integer.MIN_VALUE) {
                preHandle = 1 / x;
                n += 1;
            }
            return preHandle * pow(x, 1, Math.abs(n), sign);
        }

        public double pow(final double x, int left, int right, final int sign) {
//            System.out.println(left + "\t" + right);
            if (left > right) return 1;
            if (left == right) {
                if (sign == 1) {
                    return 1.0 / x;
                }
                return x;
            }
            int mid = (right - left) / 2 + left;
            double r1 = pow(x, left, mid, sign);
            if (r1 == 0) return 0;
            double r2 = 1;
            //较少计算量
            if ((mid - left) == (right - mid - 1)) {
                r2 = r1;
            } else {
                //right - mid - 1 <= (mid -left)
                r2 = r1 * (sign == 0 ? (1 / x) : x);
            }
//            System.out.println(left + "\t" + right + "\t" + (mid - left) + "\t" + (right - mid -1) );
            //r2 = pow(x, mid + 1, right, sign);
            return r1 * r2;
        }
    }

    public static void main(String[] args) {
        System.out.println(Math.pow(-2,-2));
        Solution solution = new Solution();
        Map<Double, Integer> map = new LinkedHashMap<>();
        map.put(0.0, 0);
        map.put(-1.0, 0);
        map.put(-2.0, -2);
        map.put(3.5, 4);
        map.put(3.3, 5);
        map.put(3.2, -100);
        map.put(-3.0, -100);
        map.put(-3.1, 100);
        map.put(99 * 1.0, Integer.MAX_VALUE);
        map.put(98 * 1.0, Integer.MIN_VALUE);
        map.put(7.0, 3);
        map.put(-7.0, -5);
        map.forEach((k, v) -> {
            double pow = solution.myPow(k, v);
            double pow1 = Math.pow(k, v);
            if (Math.abs(pow  - pow1) > Math.pow(10,-10)) {
                System.err.println("x:" + k + " n:" + v + "\tresult:" + pow + "\tpow1:" + pow1);
//                throw new RuntimeException();
            }

        });


    }
}
